public class Main {
/**
 * 思路: 找规律
 * 字符串中找最短的回文子串
 */
//    public class Main {
//        public static void main(String[] args) {
//            Scanner in = new Scanner(System.in);
//            while (in.hasNext()) { // 注意 while 处理多个 case
//                char[] str = in.next().toCharArray();
//                int n = str.length;
//                //遍历一遍找长度为2 || 3 的回文子串即可
//                boolean flag1 = false; //标记长度为2的回文子串是否存在
//                boolean flag2 = false; //标记长度为3的回文子串是否存在
//                for (int i = 0; i < n; i++) {
//                    if (i <= n - 2 && str[i] == str[i + 1]) {
//                        flag1 = true;
//                        break;
//                    } else if (i <= n - 3 && str[i] == str[i + 2]) {
//                        flag2 = true;
//                    }
//                }
//                if (flag1) {
//                    System.out.println(2);
//                } else if(flag2) {
//                    System.out.println(3);
//                } else {
//                    System.out.println(-1);
//                }
//            }
//        }
//    }


/**
 * 思路: dp 打家劫舍问题
 * 不相邻的数
 */
//    public class Main {
//        public static void main(String[] args) {
//            Scanner in = new Scanner(System.in);
//            while (in.hasNextInt()) { // 注意 while 处理多个 case
//                int n = in.nextInt();
//                int[] arr = new int[n + 1];
//                for(int i = 1; i <= n; i++) {
//                    arr[i] = in.nextInt();
//                }
//                int[] f = new int[n + 1];
//                int[] g = new int[n + 1];
//                for (int i = 1; i <= n; i++) {
//                    f[i] = arr[i] + g[i - 1];
//                    g[i] = Math.max(g[i - 1], f[i - 1]);
//                }
//                System.out.println(Math.max(g[n], f[n]));
//            }
//        }
//    }


/**
 * 空调遥控
 */
//    public class Main{
//        public static void main(String[] args) {
//            //滑动窗口法
//            Scanner in = new Scanner(System.in);
//            int n = in.nextInt();
//            int p = in.nextInt();
//            int[] arr = new int[n];
//            for(int i = 0; i < n; i++) {
//                arr[i] = in.nextInt();
//            }
//            Arrays.sort(arr);
//            int ret = 0;
//            int left = 0;
//            int right = 0;
//            while(right < n) {
//                //出窗口
//                while(arr[right] - arr[left] > 2 * p) {
//                    left++;
//                }
//                ret = Math.max(ret, right - left + 1);
//                right++;
//            }
//            System.out.println(ret);
//        }
//    }


    /**
     * 游游的重组偶数
     */
//    public class Main {
//        public static void swap(char[] s, int x, int y) {
//            char tmp = s[x];
//            s[x] = s[y];
//            s[y] = tmp;
//        }
//        public static void main(String[] args) {
//            Scanner in = new Scanner(System.in);
//            int q = in.nextInt();
//            while (q-- > 0) {
//                char[] s = (in.nextInt() + "").toCharArray();
//                int n = s.length;
//                //一个是是偶数 那么他的最后一位一定是偶数
//                //只需要将从后往前遍历 找到第一个偶数挪到最后面即可
//                for (int i = n - 1; i >= 0; i--) {
//                    if ((s[i] - '0') % 2 == 0) {
//                        swap(s, i, n - 1);
//                        break;
//                    }
//                }
//                if ( (s[n - 1] - '0') % 2 == 0) {
//                    //最后一位是偶数
//                    System.out.println(new String(s));
//                } else {
//                    System.out.println(-1);
//                }
//
//            }
//        }
//    }


    /**
     * 气球
      */
//    public class Main{
//        public static void main(String[] args) {
//            Scanner in = new Scanner(System.in);
//            int n = in.nextInt();
//            int m = in.nextInt();
//            long ret = n;
//            for(int i = 0; i < m - 1; i++) {
//                ret = ret * (n - 1) % 109;
//            }
//            System.out.println(ret);
//        }
//    }


/**
 * 走迷宫
 */
//    public class Main {
//
//        public static int n = 0;
//        public static int m = 0;
//        public static int x1 = 0;
//        public static int y1 = 0;
//        public static int x2 = 0;
//        public static int y2 = 0;
//        public static int[][] dist = new
//                int[1020][1020];//记录到达当前(i, j) 位置的最少步数
//        public static char[][] grid = new char[1020][1020];
//
//        public static void main(String[] args) {
//            Scanner in = new Scanner(System.in);
//            n = in.nextInt();
//            m = in.nextInt();
//            x1 = in.nextInt();
//            y1 = in.nextInt();
//            x2 = in.nextInt();
//            y2 = in.nextInt();
//            for (int i = 1; i <= n; i++) {
//                char[] s = in.next().toCharArray();
//                for (int j = 1; j <= m; j++) {
//                    grid[i][j] = s[j - 1];
//                }
//            }
//            //bfs
//            System.out.println(bfs());
//        }
//        static int[] dx = {0, 0, 1, -1};
//        static int[] dy = {1, -1, 0, 0};
//        public static int bfs() {
//            if (grid[x1][y1] == '*') {
//                return -1;
//            }
//            //先将dist初始化为-1 来判断该位置是否到达过
//            for (int i = 1; i <= n; i++) {
//
//                for (int j = 1; j <= m; j++) {
//                    dist[i][j] = -1;
//                }
//            }
//            //细节: 特别注意-->一定要将dist的[x1][y1] 位置初始化为0 不然会错
//            dist[x1][y1] = 0;
//            Queue<int[]> q = new LinkedList<>();
//            q.add(new int[] {x1, y1});
//            while (!q.isEmpty()) {
//                int[] index = q.poll();
//                int i = index[0];
//                int j = index[1];
//
//                for (int k = 0; k < 4; k++) {
//                    int x = i + dx[k];
//                    int y = j + dy[k];
//                    if (x >= 0 && x <= n && y >= 0 && y <= m && grid[x][y] != '*' && dist[x][y] == -1) {
//                        q.add(new int[] {x, y});
//                        dist[x][y] = dist[i][j] + 1;
//                        if (x == x2 && y == y2) {
//                            //已经找到了 谁是第一个找到的 那么谁走到当前位置的步数就是最小步数
//                            return dist[x][y];
//                        }
//                    }
//                }
//            }
//            return -1;
//        }
//    }


    /**
     *主持人调度(二)
      */
//    public class Solution {
//        public int minmumNumberOfHost (int n, int[][] startEnd) {
//            //先按照左端点排序
//            Arrays.sort(startEnd, (a, b)-> {
//                //此处细节就是注意数据越界
//                return a[0] <= b[0] ? -1 : 1;
//            });
//            //搞一个小根堆来存放已经安排好的区间的右端点的值
//            PriorityQueue<Integer> q = new PriorityQueue<>();
//            //一开是最左边的区间先给他分配一个人
//            q.offer(startEnd[0][1]);
//            for (int i = 1; i < n; i++) {
//                int left = startEnd[i][0];
//                int right = startEnd[i][1];
//                if (left >= q.peek()) {
//                    q.poll();
//                }
//                q.offer(right);
//            }
//            return q.size();
//        }
//    }


/**
 * 体操队形
 */
//    public class Main{
//        public static int[] arr = new int[15];
//        public static boolean[] visi = new boolean[15];
//        public static int n;
//        public static int ret;
//        public static void dfs(int pos) {
//            if(pos == n + 1) {
//                //能递归到n+1位置说明已经找到一种合法的排队情况了
//                ret++;
//                return;
//            }
//            for(int i = 1; i <= n; i++){
//                if(visi[i] == true) {
//                    //该数前面已经排过了
//                    continue;
//                } else if(visi[arr[i]] == true) {
//                    //要排在当前数后面的数已经排过了直接返回递归无需在往下进行
//                    return;
//                }
//                visi[i] = true;
//                dfs(pos + 1);
//                visi[i] = false;//回溯
//            }
//        }
//        public static void main(String[] args) {
//            Scanner in = new Scanner(System.in);
//            n = in.nextInt();
//            for(int i = 1; i <= n; i++) {
//                arr[i] = in.nextInt();
//            }
//            dfs(1);
//            System.out.println(ret);
//        }
//    }


    /**
     * 二叉树中的最大路径和----->树形dp问题
     */
//public class Solution {
//    int ret = -0x3f3f3f3f;//保存的是一棵树经过root的最大路径和
//    public int maxPathSum (TreeNode root) {
//        dfs(root);
//        return ret;
//    }
//    //dfs能够帮我们去找一颗树的最大单链和
//    public int dfs(TreeNode root) {
//        if(root == null) return 0;
//        int l = Math.max(dfs(root.left), 0);//得到左子树的最大单链和
//        int r = Math.max(dfs(root.right), 0);//得到右子树的最大单链和
//        ret = Math.max(l + r + root.val, ret);//在根树需要整合的信息
//        return Math.max(l , r) + root.val;
//    }
//}


    /**
     * 素数回文
      */
//
//    public class Main {
//        public static void main(String[] args) {
//            Scanner in = new Scanner(System.in);
//            String t = in.nextLong() + "";
//            String s1 = t.substring(0, t.length() - 1);
//            StringBuilder sb = new StringBuilder(s1);
//            sb.reverse();
//            String n = t + sb.toString();
//            long num = Long.parseLong(n);
//            if(isPrime(num)) {
//                System.out.println("prime");
//            } else {
//                System.out.println("noprime");
//            }
//        }
//        public static boolean isPrime(long n) {
//            if (n <= 1) return false;
//            if (n == 2) return true;
//            for (int i = 2; i <= Math.sqrt(n); i++) {
//                if (n % i == 0) {
//                    return false;
//                }
//            }
//            return true;
//        }
//    }


/**
 * 活动安排
 */
//    public class Main {
//        public static void main(String[] args) {
//            Scanner in = new Scanner(System.in);
//            int n = in.nextInt();
//            int[][] arr = new int[n][2];
//            for (int i = 0; i < n; i++) {
//                arr[i][0] = in.nextInt();
//                arr[i][1] = in.nextInt();
//            }
//            Arrays.sort(arr, (a, b) -> {
//                return a[0] - b[0];
//            });
//            int r = arr[0][1];//记录两两重合的几个区间的最小右端点
//            int ret = 1;
//            for(int i = 1; i < n; i++) {
//                if(arr[i][0] < r) {
//                    //重叠
//                    r = Math.min(r, arr[i][1]);
//                } else {
//                    ret++;
//                    r = arr[i][1];
//                }
//            }
//            System.out.println(ret);
//        }
//    }


/*

合唱团
 */
//
//    public class Main {
//        public static long INT = 0x3f3f3f3f;
//        public static void main(String[] args) {
//            Scanner in = new Scanner(System.in);
//            int n = in.nextInt();
//            int k = in.nextInt();
//            int d = in.nextInt();
//            long[] arr = new long[n + 1];
//            for(int i = 1; i <= n; i++) {
//                arr[i] = in.nextLong();
//            }
//            long[][] f = new long[n + 1][n + 1];
//            long[][] g = new long[n + 1][n + 1];
//            //初始化放在填表中
//            for (int i = 1; i <= n; i++) {
//                f[i][1] = g[i][1] = arr[i];
//                for (int j = 2; j <= Math.min(i, j); j++) {
//                    for (int prev = Math.max(i - d, j - 1); prev <= i - 1; prev++) {
//                        //此处不初始化 默认为0是不对的
//                        f[i][j] = -INT;
//                        g[i][j] = INT;
//                        f[i][j] = Math.max(Math.max(f[prev][j - 1] * arr[i], g[prev][j - 1] * arr[i]), f[i][j]);
//                        g[i][j] = Math.min(Math.min(f[prev][j - 1] * arr[i], g[prev][j - 1] * arr[i]), g[i][j]);
//                    }
//                }
//            }
//            long ret = -0x3f3f3f3f;
//            for(int i = k; i <= n; i++) {
//                ret = Math.max(ret, f[i][k]);
//            }
//            System.out.println(ret);
//
//        }
//    }


/**
 * 跳台阶扩展题
 */
//    public class Main {
//        public static void main(String[] args) {
//            Scanner in = new Scanner(System.in);
//            int n = in.nextInt();
//            System.out.println(1 << (n - 1));
//        }
//    }








}
